package com.programmercarl.greed;

/**
 * https://leetcode.cn/problems/monotone-increasing-digits/
 * 单调递增的数字  AC
 *
 * @author yulongtian
 * @create 2025-02-08 22:16
 */
public class Test15 {
    public static void main(String[] args) {
        Test15 test15 = new Test15();
        System.out.println(test15.monotoneIncreasingDigits(332));
    }

    public int monotoneIncreasingDigits(int n) {
        if (n <= 9) {
            return n;
        }
        String digit = String.valueOf(n);
        StringBuffer res = new StringBuffer();
        res.append(digit.charAt(0));
        for (int i = 1; i < digit.length(); i++) {
            if (digit.charAt(i - 1) <= digit.charAt(i)) {
                res.append(digit.charAt(i));//2332 -> 2299
            } else {
                // 233 i 2
                int j = i - 1;
                while (j >= 1 && digit.charAt(j) == digit.charAt(j - 1)) {
                    res.deleteCharAt(res.length() - 1);
                    j--;
                }
                //j=0或 digit[j-1]<digit[j]
                res.deleteCharAt(res.length() - 1);
                res.append((char) (digit.charAt(j) - 1));
                for (int k = j + 1; k < digit.length(); k++) {
                    res.append('9');
                }
                break;
            }
        }
        return Integer.parseInt(res.toString());
    }
}
